package com.sheng.leetcode.year2022.swordfingeroffer.day17;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/09/15
 *<p>
 * 剑指 Offer 41. 数据流中的中位数<p>
 *<p>
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。<p>
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。<p>
 *<p>
 * 例如，<p>
 *<p>
 * [2,3,4]的中位数是 3<p>
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5<p>
 *<p>
 * 设计一个支持以下两种操作的数据结构：<p>
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。<p>
 * double findMedian() - 返回目前所有元素的中位数。<p>
 *<p>
 * 示例 1：<p>
 * 输入：<p>
 * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]<p>
 * [[],[1],[2],[],[3],[]]<p>
 * 输出：[null,null,null,1.50000,null,2.00000]<p>
 *<p>
 * 示例 2：<p>
 * 输入：<p>
 * ["MedianFinder","addNum","findMedian","addNum","findMedian"]<p>
 * [[],[2],[],[3],[]]<p>
 * 输出：[null,null,2.00000,null,2.50000]<p>
 *<p>
 * 限制：<p>
 *<p>
 * 最多会对addNum、findMedian 进行50000次调用。<p>
 * 注意：本题与主站 295 题相同：<a href="https://leetcode-cn.com/problems/find-median-from-data-stream/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0041 {

    @Test
    public void Test01() {
        MedianFinder obj = new MedianFinder();
//        obj.addNum(1);
        obj.addNum(2);
        // 1.50000
        System.out.println(obj.findMedian());
        obj.addNum(3);
        // 2.00000
        System.out.println(obj.findMedian());
    }
}
// 1216ms
//class MedianFinder {
//
//    List<Integer> list;
//
//    /** initialize your data structure here. */
//    public MedianFinder() {
//        list = new ArrayList<>();
//    }
//
//    public void addNum(int num) {
//        list.add(num);
//        Collections.sort(list);
//    }
//
//    public double findMedian() {
//        if (list.size() % 2 == 1) {
//            // 奇数个数值时
//            return (double) list.get(list.size() / 2);
//        } else {
//            return (double) (list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2;
//        }
//    }
//}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

class MedianFinder {
    PriorityQueue<Integer> l = new PriorityQueue<>((a, b)->b-a);
    PriorityQueue<Integer> r = new PriorityQueue<>((a,b)->a-b);
    public void addNum(int num) {
        int s1 = l.size(), s2 = r.size();
        // 如果两个优先队列长度一致
        if (s1 == s2) {
            // 如果 r 队列为 null 或者 r 队列的队列头元素大于等于当前要加入队列的元素 num 时
            if (r.isEmpty() || num <= r.peek()) {
                // 将 num 元素添加到 l 队列中
                l.add(num);
            } else {
                // 否则将 r 队列的头元素删除，并添加到 l 队列队尾
                l.add(r.poll());
                // 将当前元素 num 添加到 r 队列的队尾
                r.add(num);
            }
        } else {
            // 如果 l 队列的头元素小余等于当前元素 num ，则将 num 添加到 r 队列队尾
            if (l.peek() <= num) {
                r.add(num);
            } else {
                // 否则将 l 队列的头元素删除，并添加到 r 队列队尾
                r.add(l.poll());
                // 并将当前元素添加到 l 队列的队尾
                l.add(num);
            }
        }
    }
    public double findMedian() {
        int s1 = l.size(), s2 = r.size();
        // 如果 l 队列和 r 队列的长度一致
        if (s1 == s2) {
            // 获取 l 队列和 r 队列的头元素并求平均值
            return (l.peek() + r.peek()) / 2.0;
        } else {
            // 长度不一致时，直接返回 l 队列的头元素
            return l.peek();
        }
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/by-ac_oier-exn5/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
